Generally, large amounts of data being compressed and decompressed for numerous reasons, including transmission, storage, retrieval, and processing use at some stage means of variable-length coding, such as Huffman coding. Huffman coding was originally disclosed by D. A. Huffman in an article "A Method for the Construction of Minimum Redundancy Codes" Proc. IRE, 40: 1098, 1952. In many cases, variable-length codes in an encoded bit stream are not contiguous, but are interleaved with other not-encoded bit fields. The bit fields may represent control and/or formatting information, and/or provide additional specification for encoded data including marker headers, marker codes, stuff bytes, padding bits and additional bits in, for example, JPEG encoded data.
Variable length encoding allocates codes of different lengths to different input data according to the probability of occurrence of the input data, so that statistically more frequent input codes are allocated shorter codes than the less frequent codes. The less frequent input codes are allocated longer codes. The allocation of codes may be done either statically or adaptively. For the static case, the same output code is provided for a given input datum, no matter what block of data is being processed. For the adaptive case, output codes are assigned to input data based on a statistical analysis of a particular input block or set of blocks of data, and possibly changes from block to block (or from a set of blocks to a set of blocks).
Significant problems arise when high speed decoding of variable length codes is required. Problems particularly arise when the encoded stream contains variable-length bit fields that are not encoded are interleaved with encoded data as in, for example, the JPEG standard. Greater difficulty in fast decoding of such variable-length encoded data occurs when the length of a particular not-encoded bit field can be determined only after the preceding (encoded) datum is fully decoded, as in JPEG standard. This generally excludes direct pipelining from being incorporated into a decoder, because the position of the beginning of the next encoded datum is known only after the preceding one is fully decoded.
Existing solutions either require several steps (clock cycles) to decode a single input datum, which renders them too slow for many applications, or use iterative units to decode more than one symbol quasi-simultaneously, i.e. in one stage (clock cycle). However, additional decoding blocks often make such decoders economically unjustifiable, and further are not necessarily fast enough. This is because multiple decoding units do not work fully in parallel, since the beginning of processing in the next unit still depends on the result of processing in the previous one which determines the beginning of the input data for the next one. Thus, even if decoding of several symbols takes place in one stage (clock cycle), that stage (clock period) is relatively long and the whole decoder is too slow for many applications.
Therefore, a need clearly exists for a decoder that can decode variable-length codes interleaved with variable-length bit fields that are not encoded overcoming one or more of the disadvantages of conventional decoders.